UVa/10285 - Longest run on a snowboard/10285.cpp

   1 /*
   2   Accepted
   3
   4   Andrés Mejía Posada
   5   http://blogaritmo.factorcomun.org
   6  */
   7 #include <iostream>
   8 #include <queue>
   9
  10 using namespace std;
  11
  12 int di[] = { +0, +0, +1, -1};
  13 int dj[] = { +1, -1, +0, +0};
  14
  15 int main(){
  16   int n;
  17   cin >> n;
  18   while (n--){
  19     string name;
  20     int r, c;
  21     cin >> name >> r >> c;
  22     //dp[i][j] = length of longest valid path ending at position (i,j)
  23     int g[r][c], dp[r][c];
  24     queue<pair<int, int> > q;
  25     for (int i=0; i<r; ++i){
  26       for (int j=0; j<c; ++j){
  27         cin >> g[i][j];
  28         dp[i][j] = 1;
  29         q.push(make_pair(i, j));
  30       }
  31     }
  32
  33     while (q.size()){
  34       int i = q.front().first;
  35       int j = q.front().second;
  36       q.pop();
  37
  38       for (int k=0; k<4; ++k){
  39         int ni = i + di[k];
  40         int nj = j + dj[k];
  41         if (0 <= ni && ni < r &&
  42             0 <= nj && nj < c &&
  43             g[ni][nj] < g[i][j] &&
  44             dp[ni][nj] < dp[i][j] + 1){
  45           dp[ni][nj] = dp[i][j] + 1;
  46           q.push(make_pair(ni, nj));
  47         }
  48       }
  49     }
  50     int best = -1;
  51     for (int i=0; i<r; ++i){
  52       best = max(best, *max_element(dp[i], dp[i]+c));
  53     }
  54
  55     cout << name << ": " << best << endl;
  56   }
  57   return 0;
  58 }